package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iii/'>二叉树的最近公共祖先 III(Lowest Common Ancestor of a Binary Tree III)</a>
 * <p>给定一棵二叉树中的两个节点 p 和 q，返回它们的最近公共祖先节点（LCA）。</p>
 * <p>
 * 每个节点都包含其父节点的引用（指针）。Node 的定义如下：
 * <pre>
 *         class Node {
 *              public int val;
 *              public Node left;
 *              public Node right;
 *              public Node parent;
 *          }
 *     </pre>
 * </p>
 * <p><a href='https://en.wikipedia.org/wiki/Lowest_common_ancestor'>最近公共祖先节点的定义</a>：“两个节点 p 和 q 在二叉树 T 中的最近公共祖先节点是 后代节点 中既包括 p 又包括 q 的最深节点（我们允许 一个节点为自身的一个后代节点 ）”。一个节点 x 的 后代节点 是节点 x 到某一叶节点间的路径中的节点 y。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 *                           3
 *                        /    \
 *                       5      1
 *                      / \    / \
 *                     6   2  0   8
 *                        / \
 *                       7   4
 *      输出： 3
 *      解释： 节点 5 和 1 的共同祖先节点是 3。
 *
 * 示例 2:
 *      输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 *                           3
 *                        /    \
 *                       5      1
 *                      / \    / \
 *                     6   2  0   8
 *                        / \
 *                       7   4
 *      输出： 5
 *      解释： 节点 5 和 4 的共同祖先节点是 5。根据共同祖先节点的定义，一个节点可以是自身的后代节点。
 *
 * 示例 3:
 *      输入： root = [1,2], p = 1, q = 2
 *                          1
 *                        /
 *                       2
 *      输出： 1
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中节点个数的范围是 [2, 10^4]</li>
 *     <li>-10^9 <= Node.val <= 10^9</li>
 *     <li>所有节点的值 Node.val 互不相同</li>
 *     <li>p != q</li>
 *     <li>p 和 q 存在于树中。</li>
 * </ul>
 * </p>
 * <p>
 *
 * @author c2b
 * @see LC0235LowestCommonAncestorOfABinarySearchTree_M 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)
 * @see LC0236LowestCommonAncestorOfABinaryTree_M 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)
 * @see LC1644LowestCommonAncestorOfBinaryTree_II_M 二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree II)
 * @see LC1650LowestCommonAncestorOfBinaryTree_III_M 二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree III)
 * @since 2023/12/5 11:33
 */
public class LC1650LowestCommonAncestorOfBinaryTree_III_M {

    static class Solution {
        //public Node lowestCommonAncestor(Node p, Node q) {
        //    Set<Node> parentNodeSet = new HashSet<>();
        //    while (p != null) {
        //        parentNodeSet.add(p);
        //        p = p.parent;
        //    }
        //    while (q != null) {
        //        if (parentNodeSet.contains(q)) {
        //            return q;
        //        }
        //        q = q.parent;
        //    }
        //    return null;
        //}

        public Node lowestCommonAncestor(Node p, Node q) {
            Node a = p;
            Node b = q;
            while (a != b) {
                if (a.parent == null) {
                    a = p;
                } else {
                    a = a.parent;
                }
                if (b.parent == null) {
                    b = q;
                } else {
                    b = b.parent;
                }
            }
            return a;
        }
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node parent;
    }
}
